package com.hp;

import com.hp.leetcode.dto.ListNode;

import java.util.*;

/**
 * 描述
 * 设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
 * 1. set(key, value)：将记录(key, value)插入该结构
 * 2. get(key)：返回key对应的value值
 *
 * 提示:
 * 1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。
 * 2.当缓存的大小超过K时，移除最不经常使用的记录。
 * 3.输入一个二维数组与K，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value
 *    若opt=1，接下来两个整数key, value，表示set(key, value)
 *    若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
 *    对于每个opt=2，输出一个答案
 * 4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
 *
 * 进阶:你是否可以在O(1)的时间复杂度完成set和get操作
 * 示例1
 * 输入：
 * [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
 * 复制
 * 返回值：
 * [1,-1]
 * 复制
 * 说明：
 * [1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
 * [1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
 * [1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
 * [2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
 * [1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
 * [2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
 * 示例2
 * 输入：
 * [[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2
 * 复制
 * 返回值：
 * [1,-1,-1,3,4]
 *
 * @author yunwei
 * @date 2021/8/12 13:46
 */
public class LRU {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        //设计一个map缓存
        //最近最少使用在头，最新在尾
        Map<Integer,Integer> map = new LinkedHashMap<Integer,Integer>();
        List<Integer> list = new LinkedList<Integer>();
        for(int[] operator : operators){
            int key = operator[1];
            switch(operator[0]){
                case 1:
                    int val1 = operator[2];
                    if(map.size() < k) {
                        map.put(key,val1);
                    } else{
                        Iterator it = map.keySet().iterator();
                        map.remove(it.next());
                        map.put(key,val1);
                    }
                    break;
                case 2:
                    if(map.containsKey(key)){
                        int val2 = map.get(key);
                        list.add(val2);
                        map.remove(key);
                        map.put(key,val2);
                    }else{
                        list.add(-1);
                    }
                    break;
                default:
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for(int a:list){
            res[i++] = a;
        }

        return res;
    }

    public static boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<ListNode>();
        while(head != null){
            if(set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }

}
//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode(int x) {
//        val = x;
//        next = null;
//    }
//}